/**
 * 410. 分割数组的最大值
 * https://leetcode-cn.com/problems/split-array-largest-sum/
 */
public class Solutions_410 {
    public static void main(String[] args) {
//        int[] nums = {7, 2, 5, 10, 8};
//        int m = 2;  // output: 18
//        int m = 3;  // output: 14

        int[] nums = {1, 2, 3, 4, 5};
        int m = 2;  // output: 9

//        int[] nums = {2, 3, 1, 1, 1, 1, 1};
//        int m = 5;  // output: 3

//        解释:
//        一共有四种方法将nums分割为2个子数组。
//        其中最好的方式是将其分为[7,2,5] 和 [10,8]，
//        因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

        int result = splitArray(nums, m);
        System.out.println(result);
    }

    /**
     * 解题思路：二分查找
     * 1. 通过找到 nums 数组的元素最大值以及 nums 元素累加和，确定了二分查找的边界 [left, right]
     * 2. 关键：为什么可以使用二分查找完成解题？
     *    例：int[] nums = {7, 2, 5, 10, 8};
     *       int m = 2;  // output: 18
     *       int m = 3;  // output: 14
     *
     *    将 m 看做容器，又因为要分割的是连续子数组，则可以遍历 nums 数组，从头到尾依次存放元素，若存放元素的和 sum 大于
     *    容器的容量 max，则容器需要多增加一个（即分割一次）
     *    那么如何确定容量 max 呢？
     *    因为 m 的限制是 1 <= m <= nums.length
     *    当 m = 1 时，结果为 32，即数组的累加和
     *    当 m = 5 时（数组长度），结果为 10，即数组的元素最大值
     *    那么结果一定在 [10, 32] 的区间中产生
     * 3. 若容量为 max 时（分割数组的最大值），分割成的子数组数量小于等于 m
     *          那么容量 max 还可以再小点，就可能会使子数组的长度更短，则分割的子数组数量会更多，right = mid;
     *    若容量为 max 时（分割数组的最大值），分割成的子数组数量大于 m
     *          那么容量 max 过小，必须大一点，使子数组的长度更长，则分割的子数组数量会更少，left = mid + 1
     * 4. 通过一步步缩小 [left, right] 的范围，直到 left >= right，那么最终 left 值
     *    就是将 nums 分割成 m 个子数组的所有方案中，最小的子数组最大和
     *
     */
    public static int splitArray(int[] nums, int m) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 原本存在 1 个 mid 容量的容器，用 cnt 表示数量，sum 表示已存放空间
            int cnt = 1, sum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (sum + nums[i] > mid) {
                    // 无法存放 nums[i]，需要再占用一个容器，cnt ++
                    sum = 0;
                    cnt ++;
                }
                sum += nums[i];
            }
            if (cnt <= m) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
